class Solution:
    def sortArray(self, nums: list) -> list:
        """快速排序
        """
        self.quickSort(nums, 0, len(nums) - 1)
        return nums

    def quickSort(self, array: list, left: int, right: int):
        mid = (right + left) // 2
        if right - left > 2:
            self.media3(array, left, mid, right)
            p = array[mid]
            self.swap(array, mid, right - 1)
            i = left
            j = right - 1
            while True:
                while True:
                    i += 1
                    if array[i] >= p:
                        break
                while True:
                    j -= 1
                    if array[j] <= p:
                        break
                if i < j:
                    self.swap(array, i, j)
                else:
                    break
            self.swap(array, i, right - 1)
            self.quickSort(array, left, i - 1)
            self.quickSort(array, i + 1, right)
        else:
            self.media3(array, left, mid, right)

    def media3(self, array, a, b, c):
        if array[a] > array[b]:
            self.swap(array, a, b)
        if array[a] > array[c]:
            self.swap(array, a, c)
        if array[b] > array[c]:
            self.swap(array, b, c)

    def swap(self, array, i, j):
        temp = array[i]
        array[i] = array[j]
        array[j] = temp
